public class TreeNode {

    static class Node{
        Node leftChild;
        Node rightChild;
        int val;
        public Node(int val){
            this.val=val;
        }

    }
     public Node root;

    public Node find(int val){
      Node cur=root;
      while(cur!=null){
          if(cur.val>val){
              cur=cur.leftChild;
          }
          else if(cur.val==val){
              return cur;
          }
          else if(cur.val<val){
              cur=cur.rightChild;
          }
      }
      return null;

    }

    public void insert(int val){
        if(root==null){
            root=new Node(val);
            return;
        }
        Node root1=new Node(val);
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val==val){
                return;
            }
            if(cur.val>val){
                parent=cur;
                cur=cur.leftChild;
            }
            else{
                parent=cur;
                cur=cur.rightChild;
            }

        }
        if(val> parent.val){
            parent.rightChild=root1;
        }
        if(val< parent.val){
            parent.leftChild=root1;
        }
    }
    public void inorder(Node root){
        if(root==null){
            return;
        }
        inorder(root.leftChild);
        System.out.print(root.val+" ");
        inorder(root.rightChild);

    }

    public void remove(int val){
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val==val){
remove1(parent,cur);
            }else if(cur.val>val){
                parent=cur;
                cur=cur.leftChild;
            }else{
                parent=cur;
                cur=cur.rightChild;
            }
        }
    }
    public void remove1(Node parent,Node cur){
        if(cur.leftChild==null){
            if(cur==root){
                root=cur.rightChild;
                return;
            }else if(parent.leftChild==cur){
                parent.leftChild=cur.rightChild;
                return;
            }else{
                parent.rightChild=cur.rightChild;
                return;
            }
        }else if(cur.rightChild==null){
            if(cur==root){
                root=cur.leftChild;
                return;
            }else if(parent.leftChild==cur){
                parent.leftChild=cur.leftChild;
                return;
            }else{
                parent.rightChild=cur.leftChild;
                return;
            }
        }else{
            Node target=cur.rightChild;   //找右树的最小值或找左树的最大值替换
            Node targetParent=cur;
            while(target.leftChild!=null){
                targetParent=target;
                target=target.leftChild;
            }
            cur.val=target.val;

            if(targetParent==cur){
                targetParent.rightChild=target.rightChild;
            }else{
                targetParent.leftChild=target.rightChild;
            }
        }
    }
}
